package org.autumn.structure.tree;

/**
 * 使用数组实现二叉树
 * 不可以存储0,0代表这个节点目前为空,可以改成包装类存储
 * <p>
 * 数组获取左子树的公式  编号 * 2 + 1
 * 获取右子树的公式  编号 * 2 + 2
 * <p>
 * 获取父节点的公式  (编号-1) / 2
 */
public class ArrayBinaryTree {

    int[] arr;

    public void add(int id) {
        if (arr == null) {
            arr = new int[1024];
            arr[0] = id;
        } else {
            int index = 0;
            while (true) {
                // 小于插入左子树
                if (id < arr[index]) {
                    // 获取左子树的下标
                    int left = index * 2 + 1;
                    if (arr[left] == 0) {
                        arr[left] = id;
                        return;
                    }
                    index = left;
                } else {
                    int right = index * 2 + 2;
                    if (arr[right] == 0) {
                        arr[right] = id;
                        return;
                    }
                    index = right;
                }
            }
        }
    }
    // 前序遍历
    public void preOrder(int index) {
        if (arr == null) {
            return;
        }
        System.out.print(arr[index] + "\t");

        if (arr[index * 2 + 1] != 0) {
            preOrder(index * 2 + 1);
        }

        if (arr[index * 2 + 2] != 0) {
            preOrder(index * 2 + 2);
        }

    }
}
